import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Solution {
    class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    //给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        if (k % len == 0) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        k = k % len;//这里是害怕旋转K大于链表的长度
        while (k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode cur1 = slow.next;
        slow.next = null;
        fast.next = head;
        head = cur1;//找好头结点
        return head;
    }

    //给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，
    // 只留下不同的数字 。返回 已排序的链表 。
    //第一种方法一次遍历
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode newHead = new ListNode(0, head);
        ListNode cur = newHead;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return newHead.next;
    }

    //24. 两两交换链表中的节点
    //利用栈
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        ListNode p = new ListNode(-1);
        while (cur != null && cur.next != null) {
            stack.push(cur);
            stack.push(cur.next);
            cur = cur.next.next;
            p.next = stack.pop();
            p = p.next;
            p.next = stack.pop();
        }
        if (cur != null) {
            p.next = cur;
        } else {
            p.next = null;
        }
        return p.next;
    }

    //反转链表 II
    //穿针引线
    public ListNode reverseBetween(ListNode head,
                                   int left, int right) {
        if(head==null||head.next==null){
            return  head;
        }
        ListNode dummyNode = new ListNode(0,head);
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;//这里就是left
        ListNode  ret;
        for (int i = 0; i < right - left; i++) {
            ret = cur.next;
            cur.next = ret.next;
            ret.next = pre.next;
            pre.next = ret;
        }
        return dummyNode.next;
    }
}